package 算法模板;

import java.util.Arrays;

/**
 * 快速排序（Quicksort）是对冒泡排序算法的一种改进
 * 思路：
 * 快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
 * (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
 * (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到
 * 数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中
 * 各元素都大于或等于分界值。
 * (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取
 * 一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放
 * 置较大值。右侧的数组数据也可以做类似处理。
 * (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序
 * 后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数
 * 组的排序也就完成了。
 * <p>
 * 来源：百度百科
 * <p>
 */
public class 快速排序 {

    public static void main(String[] args) {

        int[] nums = {4, 3, 2, 6, -1, 2, 4, 55, 1};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 递归：
     * 1). 定义一个分界值
     * 2). 定义左右双指针
     * 3). 找出右边比分界值大的一个元素，找出左边比分界值小的一个元素，交换位置
     * 4). 重复步骤3，得到了左区间，比分界值小的元素，右区间，比分界值大的元素
     * 5). 递归停止条件，当区间只有一个元素时，停止，即 left=right
     *
     * @param nums
     * @param start
     * @param end
     */
    public static void quickSort(int[] nums, int start, int end) {
        //递归停止条件
        if (start >= end) {
            return;
        }
        int left = start - 1, right = end + 1;
        int key = nums[start];
        while (left < right) {
            //需要的是[]里面的值，不是+1或者-1之后的值，所以前++
            //找出左边比分界值大于等于的第一个元素
            while (nums[++left] < key) ;
            //找出右边比分界值小于等于的第一个元素，可以两边都于 key 进行交互，因为两边在排序之后不影响结果
            while (nums[--right] > key) ;
            //交换位置
            if (left < right) {
                int t = nums[left];
                nums[left] = nums[right];
                nums[right] = t;
            }
        }
        //right为左边比分界值小的区间里元素的最右边元素
        quickSort(nums, start, right);
        //right+1后就是右边比
        quickSort(nums, right + 1, end);
    }

}
